// 31. 下一个排列
// 实现获取 下一个排列 的函数， 算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

// 如果不存在下一个更大的排列， 则将数字重新排列成最小的排列（ 即升序排列）。

// 必须 原地 修改， 只允许使用额外常数空间。

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  // 从右到左找到一个相邻的升序序列 a[i] < a[i+1]  ==>调整的位置
  // 从右到左找到一个数 a[k]>a[i]
  // 交换两者位置 =>然后保证[i+1,end]保持升序
  // 因为[i+1,end]是递减的 所以首尾两两交换就是递增了
  let n = nums.length
  let l = -1
  for (let i = n - 2; i >= 0; i--) {
    if (nums[i] < nums[i + 1]) {
      l = i
      break
    }
  }
  if (l > -1) {
    for (let j = n - 1; j > l; j--) {
      if (nums[l] < nums[j]) {
        swap(l, j)
        break
      }
    }
  }
  let s = l + 1,
    e = n - 1
  while (s < e) {
    swap(s, e)
    s++
    e--

  }

  function swap(i, j) {
    let temp = nums[i]
    nums[i] = nums[j]
    nums[j] = temp
  }
};
var nums = [3,2,1]
nextPermutation(nums)
console.log(nums)
